package com.cty._04_Optimization._49_UglyNumber;

/**
 * @Auther: cty
 * @Date: 2020/7/19 10:27
 * @Description: 面试题49：丑数
 * 题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到
 * 大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。
 * 习惯上我们把1当做第一个丑数。
 * @version: 1.0
 */
public class UglyNumber {
    // 方法一：蛮力法
    public static int getUglyNumber(int index){
        if(index <= 0)
            return 0;

        int number = 0;
        int uglyFound = 0;
        while(uglyFound < index){
            number++;

            if(isUglyNumber(number))
                uglyFound++;
        }
        return number;
    }  // end getUglyNumber()

    private static boolean isUglyNumber(int number){
        while(number%2 == 0)
            number /= 2;
        while(number%3 == 0)
            number /= 3;
        while(number%5 == 0)
            number /= 5;

        return number == 1;
    }  // end isUglyNumber()


    // 方法二：用空间换时间
    public static int getUglyNumber2(int index){
        if(index <= 0)
            return 0;

        int[] uglyNumbers = new int[index];
        uglyNumbers[0] = 1;
        int uglyNext = 1;
        int multiply2 = 0;
        int multiply3 = 0;
        int multiply5 = 0;

        while(uglyNext < index){
            uglyNumbers[uglyNext] = min(uglyNumbers[multiply2]*2, uglyNumbers[multiply3]*3, uglyNumbers[multiply5]*5);

            while (uglyNumbers[multiply2]*2 <= uglyNumbers[uglyNext])
                multiply2++;
            while (uglyNumbers[multiply3]*3 <= uglyNumbers[uglyNext])
                multiply3++;
            while (uglyNumbers[multiply5]*5 <= uglyNumbers[uglyNext])
                multiply5++;

            uglyNext++;
        }  // end for

        return uglyNumbers[uglyNext-1];
    }  // end getUglyNumber2()

    private static int min(int a, int b, int c){
        int maxAB = Math.min(a, b);
        int maxABC = Math.min(maxAB, c);
        return maxABC;
    }

}  // end class
